package com.xiang.xian.array;

import java.util.Arrays;

/**
 * @Author Xiang.Xian
 * @Description
 * @Date 2025/01/09/20:17
 * @Version 1.0
 */
public class MergeSortedArray {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        // 从后向前合并，以避免在nums1中合并时覆盖未处理的元素
        int i = m - 1; // nums1的有效元素末尾
        int j = n - 1; // nums2的有效元素末尾
        int k = m + n - 1; // 合并后数组的末尾

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

        // 如果nums2还有剩余元素，直接复制到nums1前面
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }

        // 如果nums1有剩余元素，它们已经在正确的位置，无需操作
    }

    public static void main(String[] args) {

        int[] nums1 = new int[999];
        nums1[0] = 1;
        nums1[1] = 2;
        nums1[2] = 3;
        nums1[3] = 7;
        nums1[4] = 8;
        nums1[5] = 9;
        int m = 6;
        int[] nums2 = {0,2, 5, 6,10,13,15,16,18,20};
        int n = nums2.length;
        merge(nums1, m, nums2, n);
        // 打印合并后的数组
        for (int num : nums1) {
            System.out.print(num + " ");
        }
    }
}
